package com.company.回溯;

import java.util.ArrayList;
import java.util.List;

public class Leet78 {
    public static int[] nums;
    /*
     * 选不选 当前节点i
     * path为路径，记录当前状态，需要回溯
     * i也可看作path当前的长度
     */
    public void dfs(List<List<Integer>> ans,List<Integer> path,int i){
        //边界条件
        if(i== nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        //不选
        dfs(ans,path,i+1);
        //选
        path.add(nums[i]);
        dfs(ans,path,i+1);
        //回溯
        path.remove(path.size()-1);
        //用 选=》回溯=》不选 的顺序也行
    }
    //从>=i的范围中选一个，再从选中的节点之后开始（保证结果递增）
    public void dfs2(List<List<Integer>> ans,List<Integer> path,int i){
        //不选
        ans.add(new ArrayList<>(path));
        //边界条件
        for (int j = i; j < nums.length; j++) {
            //选
            path.add(nums[j]);
            dfs(ans,path,j+1);
            //回溯
            path.remove(path.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        dfs(ans,path,0);
        return ans;
    }
}
